package arrAndstr;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/*
    236. 二叉树的最近公共祖先
 */
public class T236 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


    /*
      1.用 Map<TreeNode, TreeNode> 记录每个节点的父节点
      2.从p节点开始往上溯，并记录在 Set<TreeNode> visited 中汇总
      3.从q节点开始往上，如果某个节点(第一个)在 visited 中，则表示最低公共节点
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> map = new HashMap<>();
        Set<TreeNode> visited = new HashSet<>();

        // 存
        DLR(root, map);

        // p上溯
        while (true) {
            visited.add(p);
            if (!map.containsKey(p))    break;
            p = map.get(p);
        }

        // 回溯q
        while (true) {
            if (visited.contains(q))    return q;
            q = map.get(q);
        }
    }

    private void DLR(TreeNode root, Map<TreeNode, TreeNode> map) {
        if (root == null)   return;

        if (root.left != null)  map.put(root.left, root);
        if (root.right != null) map.put(root.right, root);

        DLR(root.left, map);
        DLR(root.right, map);
    }
}
